Các thuật toán Phân_tích_LU

Phân tích LU về cơ bản là một dạng của phép khử Gaussian. Ta chuyển ma trận A thành ma trận tam giác trên U bằng cách khử các phần tử bên dưới đường chéo chính. Thuật toán Doolittle khử từng cột một bắt đầu từ bên trái, bằng cách nhân bên trái A với các ma trận tam giác dưới. Kết quả của thuật toán này là một ma trận tam giác dưới đơn vị và một ma trận tam giác trên. Thuật toán Crout hơi khác ở chỗ tạo thành một ma trận tam giác dưới và một ma trận tam giác trên đơn vị.

Phân tích LU sử dụng các thuật toán này yêu cầu khoảng 2n3 / 3 phép tính dấu chấm động.

Thuật toán Doolittle

Cho một ma trận N × N

A = ( a n , n ) {\displaystyle A=(a_{n,n})}

ta định nghĩa

A ( 0 ) := A {\displaystyle A^{(0)}:=A}

và lặp với n = 1,...,N-1 như sau.

Khử các phần tử bên dưới đường chéo chính của cột thứ ncủa A(n-1)bằng cách cộng vào dòng thứ i của ma trận này với dòng thứ n và nhân thêm hệ số

l i , n := − a i , n ( n − 1 ) a n , n ( n − 1 ) {\displaystyle l_{i,n}:=-{\frac {a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}}}

với i = n + 1 , … , N {\displaystyle i=n+1,\ldots ,N} . Nói cách khác, ta nhân bên tráiA(n-1) với ma trận tam giác dưới

L n = ( 1 0 ⋱ 1 l n + 1 , n ⋱ ⋮ ⋱ 0 l N , n 1 ) . {\displaystyle L_{n}={\begin{pmatrix}1&&&&&0\\&\ddots &&&&\\&&1&&&\\&&l_{n+1,n}&\ddots &&\\&&\vdots &&\ddots &\\0&&l_{N,n}&&&1\\\end{pmatrix}}.}

Đặt

A ( n ) := L n A ( n − 1 ) . {\displaystyle A^{(n)}:=L_{n}A^{(n-1)}.}

Sau N-1 bước, ta đã khử tất cả các phần tử bên dưới đường chéo chính, và nhận được ma trận tam giác trênA(N-1). Phép phân tích LU được xác định bằng nhận xét rằng

A = L 1 − 1 L 1 A ( 0 ) = L 1 − 1 A ( 1 ) = L 1 − 1 L 2 − 1 L 2 A ( 1 ) = L 1 − 1 L 2 − 1 A ( 2 ) = … = L 1 − 1 … L N − 1 − 1 A ( N − 1 ) . {\displaystyle A=L_{1}^{-1}L_{1}A^{(0)}=L_{1}^{-1}A^{(1)}=L_{1}^{-1}L_{2}^{-1}L_{2}A^{(1)}=L_{1}^{-1}L_{2}^{-1}A^{(2)}=\ldots =L_{1}^{-1}\ldots L_{N-1}^{-1}A^{(N-1)}.}

Ký hiệu ma trận tam giác trênA(N-1) là U, và L = L 1 − 1 … L N − 1 − 1 {\displaystyle L=L_{1}^{-1}\ldots L_{N-1}^{-1}} . Vì nghịch đảo của ma trận tam giác dưới 'Ln cũng là ma trận tam giác dưới, và tích hai ma trận tam giác dưới cũng là một ma trận tam giác dưới nên L là ma trận tam giác dưới cần tìm.Hơn nữa, nhận xét rằng

L = ( 1 0 − l 2 , 1 ⋱ 1 ⋮ − l n + 1 , n ⋱ ⋮ 1 − l N , 1 − l N , n − l N , N − 1 1 ) . {\displaystyle L={\begin{pmatrix}1&&&&&0\\-l_{2,1}&\ddots &&&&\\&&1&&&\\\vdots &&-l_{n+1,n}&\ddots &&\\&&\vdots &&1&\\-l_{N,1}&&-l_{N,n}&&-l_{N,N-1}&1\\\end{pmatrix}}.}

Vậy ta có A = L U {\displaystyle A=LU} .

Rõ ràng là để thuật toán hoạt động được, cần phải đảm bảo a n , n ( n − 1 ) ≠ 0 {\displaystyle a_{n,n}^{(n-1)}\not =0} tại mỗi bước (xem công thức l i , n {\displaystyle l_{i,n}} ). Nếu giả sử này không đúng ở một bước nào đó, ta có thể hoán vị dòng thứ n với một dòng khác bên dưới nó để tiếp tục thuật toán. Đây là lý do mà phép phân tích LU tổng quát tương tự với phép phân tích P − 1 A = L U {\displaystyle P^{-1}A=LU} .

Thuật toán Crout và LUP

Thuật toán phân tích LUP của Cormen et al. là trường hợp tổng quát của phép phân tích Crout. Phần này trình bày thuật toán phân tích LUP.

  1. Nếu A {\displaystyle A} có một phần tử khác không trong dòng đầu tiên, chọn ma trận hoán vị P 1 {\displaystyle P_{1}} sao cho A P 1 {\displaystyle AP_{1}} có phần tử khác không ở góc trên trái. Ngược lại, chọn P 1 {\displaystyle P_{1}} là ma trận đơn vị. Đặt A 1 = A P 1 {\displaystyle A_{1}=AP_{1}} .
  2. Gọi A 2 {\displaystyle A_{2}} là ma trận có được từ A 1 {\displaystyle A_{1}} bằng cách bỏ đi cột đầu tiên và dòng đầu tiên của nó. Phân tích A 2 = L 2 U 2 P 2 {\displaystyle A_{2}=L_{2}U_{2}P_{2}} theo đệ quy. Tạo L {\displaystyle L} từ L 2 {\displaystyle L_{2}} bằng cách thêm một dòng 0 vào phía trên và thêm cột đầu tiên của A 1 {\displaystyle A_{1}} vào bên trái.
  3. Tạo U 3 {\displaystyle U_{3}} từ U 2 {\displaystyle U_{2}} bằng cách thêm một dòng không vào phía trên và một cột không vào bên trái, sau đó thay phần tử ở góc trên trái (đang bằng 0) thành 1. Tạo P 3 {\displaystyle P_{3}} từ P 2 {\displaystyle P_{2}} theo cách tương tự và định nghĩa A 3 = A 1 / P 3 = A P 1 / P 3 {\displaystyle A_{3}=A_{1}/P_{3}=AP_{1}/P_{3}} . Gọi P {\displaystyle P} là nghịch đảo của P 1 / P 3 {\displaystyle P_{1}/P_{3}} .
  4. Lúc này, A 3 {\displaystyle A_{3}} bằng L U 3 {\displaystyle LU_{3}} , (có thể) ngoại trừ dòng đầu tiên. Nếu dòng đầu tiên của A {\displaystyle A} là 0, thì A 3 = L U 3 {\displaystyle A_{3}=LU_{3}} vì cả hai đều có dòng đầu tiên là 0, và theo đó A = L U 3 P {\displaystyle A=LU_{3}P} . Ngược lại, A 3 {\displaystyle A_{3}} và L U 3 {\displaystyle LU_{3}} có cùng phần tử khác 0 ở góc trên trái, và A 3 = L U 3 U 1 {\displaystyle A_{3}=LU_{3}U_{1}} với ma trận vuông tam giác trên U 1 {\displaystyle U_{1}} với các phần tử đường chéo bằng 1 ( U 1 {\displaystyle U_{1}} khử các phần tử của L U 3 {\displaystyle LU_{3}} và thêm các phần tử của A 3 {\displaystyle A_{3}} ). Khi đó A = L U 3 U 1 P {\displaystyle A=LU_{3}U_{1}P} là phép phân tích cần tìm.

Đoạn mã giả sau thể hiện từng bước của thuật toán phân tích LUP:

// A: input - ma trận ban đầu, kích thước n x n.// n: input - kích thước của A.// C: output - ma trận kích thước (n x n+1),...//              với n cột đầu tiên chứa L và U,...//              cột cuối cùng thể hiện ma trận hoán vị P.FUNCTION LUP(n, A; C)     // khởi tạo C    FOR i=1 TO n DO        C[i;n+1] = i             // khởi tạo p        FOR j=1 TO n DO            C[i,j] = A[i,j]        END    END    FOR j=1 TO n-1 DO           // với mỗi cột j        Chọn phần tử khác 0 lớn nhất (phần tử neo) trong cột j.        Gọi i là dòng chứa phần tử neo đó.        IF không tìm được i THEN            NGỪNG THUẬT TOÁN    // Không có lời giải duy nhất        END        IF i ~= j THEN            Đảo dòng i và j        END        FOR i = j + 1 TO n DO   // với mỗi dòng bên dưới dòng thứ j            t = C[i,j]/C[j,j]   // thừa số            C[i, j] = t            FOR k = j+1 TO n DO                // với mỗi cột bên phải cột j                C[i,k] = C[i,k] - t*C[j,k]            END        END    ENDEND

Độ phức tạp lý thuyết

Nếu nhân hai ma trận bậc n có độ phức tạp M(n), trong đó M(n)≥na với a>2 nào đó, thì phép phân tích LU có thể được tính trong thời gian O(M(n)).[1] Nghĩa là, chẳng hạn dựa trên thuật toán Coppersmith–Winograd, ta có thể có thuật toán phân tích LU với độ phức tạp O(n2.376).